//
//  SceneDelegate.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/11/18.
//

import UIKit
import SwiftUI

class SceneDelegate: UIResponder, UIWindowSceneDelegate {

    var window: UIWindow?


    func scene(_ scene: UIScene, willConnectTo session: UISceneSession, options connectionOptions: UIScene.ConnectionOptions) {
        // Use this method to optionally configure and attach the UIWindow `window` to the provided UIWindowScene `scene`.
        // If using a storyboard, the `window` property will automatically be initialized and attached to the scene.
        // This delegate does not imply the connecting scene or session are new (see `application:configurationForConnectingSceneSession` instead).

        // Create the SwiftUI view that provides the window contents.
        let contentView = ContentView()

        // Use a UIHostingController as window root view controller.
        if let windowScene = scene as? UIWindowScene {
            let window = UIWindow(windowScene: windowScene)
            window.rootViewController = UIHostingController(rootView: contentView)
            self.window = window
            window.makeKeyAndVisible()
        }
    }

    func sceneDidDisconnect(_ scene: UIScene) {
        // Called as the scene is being released by the system.
        // This occurs shortly after the scene enters the background, or when its session is discarded.
        // Release any resources associated with this scene that can be re-created the next time the scene connects.
        // The scene may re-connect later, as its session was not necessarily discarded (see `application:didDiscardSceneSessions` instead).
    }

    func sceneDidBecomeActive(_ scene: UIScene) {
        // Called when the scene has moved from an inactive state to an active state.
        // Use this method to restart any tasks that were paused (or not yet started) when the scene was inactive.
        // 二分查找
//        let arr = [2,4,5,7,8,9,12,12,12,23,34,34,44,55,56]
//        let index = BinarySearch.binarySearch(fromSource: arr, value: 2)
//        print(BinarySearch.recursionBinarySearch(fromSource: arr, value: 55))// 二分递归查找
//        print(BinarySearch.square(value: 18))// 求平方根
//        print(BinarySearch_16.find(firstOneEquelValue: 12, arr: arr))// 查找第一个值等于给定值的元素
//        print(BinarySearch_16.find(lastOnEqualValue: 12, arr: arr))// 查找最后一个值等于给定值的元素
//        print(BinarySearch_16.find(firstOneGreaterThanOrEqualValue: 10, arr: arr))
//        print(BinarySearch_16.find(lastOneLessThanOrEqualVlaue: 10, arr: arr))
        
        // 跳表查询
//        var node: ListNode? = ListNode.init(0).next
//        var tempNode:ListNode? = nil
//        for index in 0..<1000 {
//            let add_node: ListNode? = ListNode.init(index)
//            if index == 0 {
//                tempNode = add_node
//                node = tempNode
//            } else {
//                tempNode?.next = add_node
//                tempNode = tempNode?.next
//            }
//        }
//
//        let result: ListNode? = SkipTableQuery_17.query(node, value: 2)
//        print(result as Any)
        
        // 二叉树
//        let node1:BinaryListNode? = BinaryListNode.init(10)
//        let node2:BinaryListNode? = BinaryListNode.init(14)
//        let node3:BinaryListNode? = BinaryListNode.init(18)
//        let node4:BinaryListNode? = BinaryListNode.init(22)
//        let node5:BinaryListNode? = BinaryListNode.init(26)
//        let node6:BinaryListNode? = BinaryListNode.init(30)
//        let node7:BinaryListNode? = BinaryListNode.init(34)
//        let node8:BinaryListNode? = BinaryListNode.init(38)
//        let node9:BinaryListNode? = BinaryListNode.init(43)
//        let node10:BinaryListNode? = BinaryListNode.init(47)
//        let node11:BinaryListNode? = BinaryListNode.init(52)
//        let node12:BinaryListNode? = BinaryListNode.init(57)
//        let node13:BinaryListNode? = BinaryListNode.init(70)
//        let node14:BinaryListNode? = BinaryListNode.init(78)
//        let node15:BinaryListNode? = BinaryListNode.init(88)
//        let node16:BinaryListNode? = BinaryListNode.init(96)
// MARK:-二叉树遍历
//        // 根节点node1
//        node1?.left = node2
//        node1?.right = node3
//        node2?.pre = node1
//        node3?.pre = node1
//        // 子节点node2
//        node2?.left = node4
//        node2?.right = node5
//        node4?.pre = node2
//        node5?.pre = node2
//        // 子节点node3
//        node3?.left = node6
//        node3?.right = node7
//        node6?.pre = node3
//        node7?.pre = node3
//        // 子节点node4
//        node4?.left = node8
//        node4?.right = node9
//        node8?.pre = node4
//        node9?.pre = node4
//        // 子节点node5
//        node5?.left = node10
//        node5?.right = node11
//        node10?.pre = node5
//        node11?.pre = node5
//        // 子节点node6
//        node6?.left = node12
//        node6?.right = node13
//        node12?.pre = node6
//        node13?.pre = node6
//        // 子节点node7
//        node7?.left = node14
//        node7?.right = node15
//        node14?.pre = node7
//        node15?.pre = node7
//        // 子节点node8
//        node8?.left = node16
//        node16?.pre = node8
        
        // 前序遍历
//        BinaryTree_18.traversal(frontWithNode: node1)
        // 中序遍历
//        BinaryTree_18.traversal(middleWithNode: node1)
        // 后序遍历
//        BinaryTree_18.traversal(behindWithNode: node1)
        
        // MARK:- 二叉查找树
        // 创建一个二叉查找树
//        let newNode: BinaryListNode? = node8
//        newNode?.left = node4
//        newNode?.right = node13
//        node4?.left = node2
//        node4?.right = node6
//        node13?.left = node10
//        node13?.right = node15
//        node2?.left = node1
//        node2?.right = node3
//        node6?.left = node5
//        node6?.right = node7
//        node10?.left = node9
//        node10?.right = node12
//        node15?.left = node14
//        node15?.right = node16
//        node12?.left = node11
        // 遍历二叉查找树
//        BinaryTree_18.traversal(middleWithNode: newNode)
        // 在二叉查找树中查找
//        let findNode = BinaryFindTree.find(treeNode: newNode, findValue: 38)
        // 插入
//        let insertN: BinaryListNode? = BinaryListNode.init(9)
//        let insertResult = BinaryFindTree.insert(tree: newNode, insertNode: insertN)
        // 删除某个节点
//        BinaryFindTree.delet(newNode, deletValue: 99)
//        BinaryTree_18.traversal(middleWithNode: newNode)
        // 获取二叉查找树的高度
//        print(BinaryFindTree.getHeight(tree: newNode))
        
        // MARK:- 堆排序
//        let arr = [10,9,4,23,33,41,5,34,54,91,87,22]
        // 从头往后建堆
//        let heap = HeapSort.create(fromFirst: arr)
        // 从最后的非叶子节点往前建堆
//        let heap = HeapSort.create(fromBack: arr)
//        for item in heap.a {
//            print(item)
//        }
        // 删除 堆顶节点
//        heap.deletTop()
//        print("-----分割线-----")
//        for item in heap.a {
//            print(item)
//        }
        
        // 插入值
//        heap.insert(100)
//        print("-----分割线-----")
//        for item in heap.a {
//            print(item)
//        }
        
        // 堆排序
//        heap.sort()
//        for item in heap.a {
//            print(item)
//        }
        
        // 4个有序数组合成一个大的有序数组
//        var arrs = [[HeapNode]]()
//        for ind in 0...5 {
//            var tempArr = [HeapNode]()
//
//            for index in 0...4 {
//                let heapNode = HeapNode(ind + index * 6, flag: ind, index: index)
//                tempArr.append(heapNode)
//            }
//            arrs.append(tempArr)
//        }
//        let result = HeapSort.merge(manyOrderlyArr: arrs)
//        result.map {
//            print($0.value)
//        }
        // 高性能定时器
//        var arrs = [HeapNode]()
//
//        for ind in 0...5 {
//            let dateFormat = DateFormatter()
//            dateFormat.dateFormat = "yyyy-MM-dd HH:mm:ss"
//            let date = dateFormat.date(from: "2020-12-24 \(18 + ind):06:06")
//            let timeInterval: TimeInterval = date!.timeIntervalSince1970
//            let heapNode = HeapNode(Int(timeInterval), flag: ind)
//            arrs.append(heapNode)
//        }
//        for _ in 0...arrs.count - 1 {
//            let result = HeapSort.efficientTimer(triggerTime: &arrs)
//            print(result?.value as Any)
//        }
        
        // 字符匹配之BF算法
//        let star1 = CFAbsoluteTimeGetCurrent()
//        let result1 = StringMatching.bruteForce("syfhasjdfsadyfhjasdfyashjfasfyshjfythjgeryhjdfscatfgshsdftyashjdxxfsayfhjsdfasyhfjasdfasyujgkasdtgyfhjdsakfsadyfuajskfgasdvctyhjkfascdfatsyfuiekolfcsyhsajkfdsdayfuajskdfldsafyasujifklasdfsdhjfksadfyhjkfghjdrdertyuiasfdhfsafsdffstyhujkfgvbtyhjasfdyhjsafyshjfasyfhasjdfsadyfhjasdfyashjfasfccyshjfythjgeryhjdfscatfgshsdftyashjdfsayfhjsdfasyhfjasdfasyujgkasdtgyfhjdsakfsadyfuajskfgasdvctyhjkfascdfatsyfuiekolfcsyhsajkfdsdayfuajskdfldsafyasujifklasdfsd", patternString: "shjdxx")
//        let time1 = CFAbsoluteTimeGetCurrent() - star1
//        print("BF算法匹配结果:\(result1),匹配时间：\(time1)")
        // 字符串匹配之BF算法（二维数组）
//        let star1 = CFAbsoluteTimeGetCurrent()
//        let hostArrs = [["d","a","b","c"],
//                        ["e","f","a","d"],
//                        ["c","c","a","f"],
//                        ["d","e","f","c"]
//        ]
//
//        let patternArrs = [["c","a"],
//                           ["e","f"]
//        ]
//        let result1 = StringMatching.bruteForceTwoDimensional(hostArrs, patternArr: patternArrs)
//        let time1 = CFAbsoluteTimeGetCurrent() - star1
//        print("BF算法匹配结果:\(result1),匹配时间：\(time1)")
        // 字符匹配之RK算法
//        let star2 = CFAbsoluteTimeGetCurrent()
//        let result2 = StringMatching.rabinKarp("syfhasjdfsadyfhjasdfyashjfasfyshjfythjgeryhjdfscatfgshsdftyashjdxxfsayfhjsdfasyhfjasdfasyujgkasdtgyfhjdsakfsadyfuajskfgasdvctyhjkfascdfatsyfuiekolfcsyhsajkfdsdayfuajskdfldsafyasujifklasdfsdhjfksadfyhjkfghjdrdertyuiasfdhfsafsdffstyhujkfgvbtyhjasfdyhjsafyshjfasyfhasjdfsadyfhjasdfyashjfasfccyshjfythjgeryhjdfscatfgshsdftyashjdfsayfhjsdfasyhfjasdfasyujgkasdtgyfhjdsakfsadyfuajskfgasdvctyhjkfascdfatsyfuiekolfcsyhsajkfdsdayfuajskdfldsafyasujifklasdfsd", patternString: "shjdxx")
//        let time2 = CFAbsoluteTimeGetCurrent() - star2
//        print("RK算法匹配结果:\(result2),匹配时间：\(time2)")
        
        // MARK:- 分治算法求逆序度
//        var arr = [87,45,34,99,80,23]
//        print("目标数组的逆序度为：\(DivideAndConquer.count(&arr))")
        // MARK:- 八皇后
//        Backtracking.cal8Queues(0)
        // MARK:- 背包问题
//        Backtracking.backpack0_1(whitchOne: 0, currentWeight: 0, items: [7, 4, 9, 3, 10], count: 5, capacity: 20)
//        print(Backtracking.maxWeight)
        // MARK:- 正则表达式
//        let regu = Backtracking(regular: ["a","b","?","o","d"], exprLength: 5)
//        print(regu.match(["a","b","c","o","f"], length: 5))
        
        // MARK:-动态规划
//        print(DynamicPlanning.pocketMaxLoad(owned: [2, 2, 4, 6, 3], max: 9))
//        print(DynamicPlanning.pocketMaxLoadWithValue2(goods:[2,2,4,6,3], [3,4,8,9,6], max: 9))
//        print(DynamicPlanning.shortWay(yanghuiTriangle: [[5],[7,8],[2,3,4],[4,9,6,1],[2,7,9,4,5]]))
//        print(DynamicPlanning.minimumCoins(to: 12, coins: [1,3,5,7,2,8]))
//        print(DynamicPlanning.shortPath([[1,3,5,9],[2,1,3,4],[5,2,6,7],[6,8,4,3]]))
        // 求两个字符串的莱文斯坦距离
//        print(DynamicPlanning.lwstDistance(["m","i","t","c","m","u"], ["m","t","a","c","n","u"]))
        // 求两个字符串的最长公共子串长度
//        print(DynamicPlanning.longestCommonSubstring(["m","i","t","c","m","u"], ["m","t","a","c","n","u"]))
        // 练习题
//        print(DynamicPlanning.increasingSubsequence(for: ["2","9","3","6","5","1","7","8"]))
        
        
        
    }

    func sceneWillResignActive(_ scene: UIScene) {
        // Called when the scene will move from an active state to an inactive state.
        // This may occur due to temporary interruptions (ex. an incoming phone call).
    }

    func sceneWillEnterForeground(_ scene: UIScene) {
        // Called as the scene transitions from the background to the foreground.
        // Use this method to undo the changes made on entering the background.
    }

    func sceneDidEnterBackground(_ scene: UIScene) {
        // Called as the scene transitions from the foreground to the background.
        // Use this method to save data, release shared resources, and store enough scene-specific state information
        // to restore the scene back to its current state.
    }


}

